package main.leetcode.clockin.July;

import main.datastruc.TreeNode;

/**
 * 108. 将有序数组转换为二叉搜索树
 *
 * <p>将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
 *
 * <p>本题中，一个高度平衡二叉树是指一个二叉树 **每个节点** 的左右两个子树的高度差的绝对值不超过 1。
 */
public class day3 {
    public static void main(String[] args) {
        System.out.println(new day3().sortedArrayToBST(new int[] {-10, -3, 0, 5, 9}));
    }

    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums == null || nums.length == 0) {
            return null;
        }
        return creBST(nums, 0, nums.length - 1);
    }

    private TreeNode creBST(int[] nums, int l, int r) {
        if (l > r) {
            return null;
        }
        int mid = l + (r - l >> 1);
        TreeNode root = new TreeNode(nums[mid]);
        root.left = creBST(nums, l, mid - 1);
        root.right = creBST(nums, mid + 1, r);
        return root;
    }

    private void creBST(int num, TreeNode root) {
        TreeNode node = root;
        while (node != null) {
            if (num < node.val) {
                if (node.left == null) {
                    node.left = new TreeNode(num);
                    break;
                } else {
                    node = node.left;
                }
            } else {
                if (node.right == null) {
                    node.right = new TreeNode(num);
                    break;
                } else {
                    node = node.right;
                }
            }
        }
    }
}
